真心巧妙,不看题解准做不出(之前题解都看不懂QwQ)
这道题貌似有许多的做法,都不费,主席树的话不知道怎么搞,于是建了 $3$ 棵线段树,实测是不会炸的。
30分做法:
小学生都能轻易想出来的解法,对于一个询问的区间,暴力枚举其子区间,然后按照题面的要求算贡献,区间最大值可以用 $ST$ 表预处理,复杂度爆炸,但是仍然可以拿到 $30$ 暴力分。
1 |
|
100分做法
对于一个点 $i$ ,我们设 $lmax[i]$ 为 $i$ 向左走遇到的第一个大于自己的数(没有的话为 $0$) ,同样的,设 $rmax[i]$ 为 $i$ 向右走遇到的第一个大于自己的数(没有的话为 $n+1$) 。这两个数组比较容易求出,搞个单调栈求就好。
1 | top=0,stack[0]=0; |
然后可以发现,如果枚举点 $i$ 的话,有了上面的两个数组后有关 $i$ 的贡献就好求些了,首先我们可以知道 $i$ 是区间 $[lmax[i]+1,rmax[i]-1]$ 的最大值,那么对于每种贡献:
- 如果 $lmax[i]$ 和 $rmax[i]$ 都在当前询问区间内,那么就可以做出 $p_1$ 的贡献。
- 如果 $lmax[i]$ 在当前询问区间中,那么显然 $lmax[i]$ 为区间 $[lmax[i],rmax[i]-1]$ 的最大值,这个时候右端点如果在 $[i+1,rmax[i]-1]$ 区间中,那么可以保证右端点不是 $[lmax[i],rmax[i]-1]$ 的次大值,这个时候可以产生多个 $p_2$ 的贡献。
- 如果 $rmax[i]$ 在当前询问区间中,那么显然当左端点为 $[lmax[i]+1,i-1]$ 的时候该子区间均能产生 $p_2$ 的贡献,原因跟上面一样的。
但是这样的话复杂度依旧是 $O(n^2)$ 的,所以还要优化。
考虑用线段树维护,我们离线处理询问,把每个询问按左端点排个序,然后反着扫一遍,如果遇到了一个点 $x$ ,它是 某个点/某些点 的 $lmax$ ,假设 $x$ 是 $i$ 的 $lmax$ ,那么我们依次在第一颗线段树中实现区间加:将 $[i+1,rmax[i]-1]$ 区间正题加上 $p_2$ ,因为当前的左端点为 $x$ ,这个时候我们将要计算的是所有的左端点为 $x$ 的区间对答案的贡献,因为对于 $i$ 来说右端点的范围就是 $[i+1,rmax[i]-1]$,这些区间均可以做出贡献,于是都在线段树中加上。当然在做贡献的之前不要忘记判断 $i+1<rmax[i]$ ,如果不满足的话就没有右端点了……
那么接下来讨论怎么计算 $p_1$ 的贡献,对于询问区间来说,现在我们确定了左端点为 $x$ ,这个时候当右端点落在 $[rmax[i],n+1]$ 的时候询问区间都可以算上 $[lmax[i],rmax[i]]$ 区间的贡献,也就是 $p_1$ 的贡献,于是我们可以在另一个线段树中将 $[rmax[i],n+1]$ 全都加上 $p_1$ 即可。
按照上面的方法,再正着扫一遍计算 $rmax$ 的情况就好,当然反着扫的时候就不要算 $p_1$ 的贡献了,不然就会重复了,想想就可以明白。最后就是一定要开 $longlong$ 。
Code:
1 |
|
本文标题:【题解】 [AH2017/HNOI2017]影魔 线段树 luoguP3722/bzoj4826
文章作者:Qiuly
发布时间:2019年03月15日 - 00:00
最后更新:2019年03月29日 - 13:52
原始链接:http://qiulyblog.github.io/2019/03/15/[题解]bzoj4826/
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。